package binaryTree;

import org.junit.Test;

import java.util.*;

/**
 * @author king
 */
public class InorderTraversal {
	
	/** 递归中序遍历 */
	@Test
	public LinkedList<Integer> reInorderTrav(TreeNode root){
		//存储遍历结果
		LinkedList<Integer> nodes = new LinkedList<>();
		dfs(root, nodes);
		return nodes;
	}

	private void dfs(TreeNode root, LinkedList<Integer> nodes){
		if(root != null){
			dfs(root.left, nodes);
			nodes.offer(root.val);
			dfs(root.right, nodes);
		}
	}

	/** 迭代中序遍历 */
	public LinkedList<Integer> loopInorderTrav(TreeNode root){
		//存储遍历结果
		LinkedList<Integer> nodes = new LinkedList<>();
		//ArrayDeque模拟栈
		Deque<TreeNode> stack = new ArrayDeque<>();
		TreeNode curNode = root;
		while(curNode != null || !stack.isEmpty()){
			//左子树
			while(curNode != null){
				//结点入栈，用于获取结点数据和遍历右子树
				stack.offerLast(curNode);
				curNode = curNode.left;
			}
			//根
			curNode = stack.pollLast();
			nodes.offer(curNode.val);
			//右子树
			curNode = curNode.right;
		}
		return nodes;
	}
}

class TreeNode {
	int val;
	TreeNode left;
	TreeNode right; 

	public TreeNode(int val){
		this.val = val;
	}
}
